{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Cost to Merge Stones"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: mergeStones"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #合并石头的最低成本"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有 <code>n</code> 堆石头排成一排，第 <code>i</code> 堆中有&nbsp;<code>stones[i]</code>&nbsp;块石头。</p>\n",
    "\n",
    "<p>每次 <strong>移动</strong> 需要将 <strong>连续的</strong> <code>k</code> 堆石头合并为一堆，而这次移动的成本为这 <code>k</code> 堆中石头的总数。</p>\n",
    "\n",
    "<p>返回把所有石头合并成一堆的最低成本。如果无法合并成一堆，返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>stones = [3,2,4,1], K = 2\n",
    "<strong>输出：</strong>20\n",
    "<strong>解释：</strong>\n",
    "从 [3, 2, 4, 1] 开始。\n",
    "合并 [3, 2]，成本为 5，剩下 [5, 4, 1]。\n",
    "合并 [4, 1]，成本为 5，剩下 [5, 5]。\n",
    "合并 [5, 5]，成本为 10，剩下 [10]。\n",
    "总成本 20，这是可能的最小值。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>stones = [3,2,4,1], K = 3\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>任何合并操作后，都会剩下 2 堆，我们无法再进行合并。所以这项任务是不可能完成的。.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>stones = [3,5,1,2,6], K = 3\n",
    "<strong>输出：</strong>25\n",
    "<strong>解释：</strong>\n",
    "从 [3, 5, 1, 2, 6] 开始。\n",
    "合并 [5, 1, 2]，成本为 8，剩下 [3, 8, 6]。\n",
    "合并 [3, 8, 6]，成本为 17，剩下 [17]。\n",
    "总成本 25，这是可能的最小值。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == stones.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 30</code></li>\n",
    "\t<li><code>1 &lt;= stones[i] &lt;= 100</code></li>\n",
    "\t<li><code>2 &lt;= k &lt;= 30</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-cost-to-merge-stones](https://leetcode.cn/problems/minimum-cost-to-merge-stones/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-cost-to-merge-stones](https://leetcode.cn/problems/minimum-cost-to-merge-stones/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,4,1]\\n2', '[3,2,4,1]\\n3', '[3,5,1,2,6]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "\n",
    "        if (n-1) % (k-1) != 0:\n",
    "            return -1\n",
    "\n",
    "        s = [0] + stones\n",
    "        # presum list\n",
    "        for i in range(1,len(stones)+1):\n",
    "            s[i] += s[i-1]\n",
    "        # print(s)\n",
    "\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            dp[i][i] = 0\n",
    "            for j in range(i+1, n):\n",
    "                res = min(dp[i][m] + dp[m+1][j] for m in range(i, j, k-1))\n",
    "                if (j-i) % (k-1) == 0:\n",
    "                    res += s[j+1] - s[i]\n",
    "                \n",
    "                dp[i][j] = res \n",
    "        \n",
    "        return dp[0][n-1]\n",
    "\n",
    "        # @cache \n",
    "        # def dfs(i, j):\n",
    "        #     if i == j:\n",
    "        #         return 0\n",
    "        #     res = min(dfs(i, m) + dfs(m+1, j) for m in range(i, j, k-1))\n",
    "        #     if (j-i) % (k-1) == 0:\n",
    "        #         res += s[j+1] - s[i]\n",
    "        #     return res\n",
    "        # return dfs(0, n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1):  # 无法合并成一堆\n",
    "            return -1\n",
    "        s = list(accumulate(stones, initial=0))  # 前缀和\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                f[i][j] = min(f[i][m] + f[m + 1][j] for m in range(i, j, k - 1))\n",
    "                if (j - i) % (k - 1) == 0:  # 可以合并成一堆\n",
    "                    f[i][j] += s[j + 1] - s[i]\n",
    "        return f[0][-1]\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/minimum-cost-to-merge-stones/solutions/2207235/tu-jie-qu-jian-dpzhuang-tai-she-ji-yu-yo-ppv0/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int],K: int) -> int:\n",
    "        if (len(stones)-1)%(K-1) != 0:\n",
    "            return -1\n",
    "        n = len(stones)\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        ss = [0 for _ in range(n+1)]\n",
    "\n",
    "        for i in range(n+1):\n",
    "            ss[i] = ss[i-1] + stones[i-1]\n",
    "\n",
    "        # i ... j 区间, 满足合并k的最小成本\n",
    "        # step 必为k-1的倍数 而 [i][j][k-1]必然已经被计算过最优解\n",
    "        # 还需要计算切分点\n",
    "        # 如此可知状态转移方程\n",
    "        dp = [[[float('inf') for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            dp[i][i][1] = 0\n",
    "        \n",
    "        for l in range(2, n+1):\n",
    "            for i in range(1, n+2-l):\n",
    "                j = l + i - 1\n",
    "                for k in range(2, K+1):\n",
    "                    for m in range(i, j):\n",
    "                        dp[i][j][k] = min(dp[i][j][k], dp[i][m][k-1] + dp[m+1][j][1])\n",
    "                dp[i][j][1] = min(dp[i][j][1], dp[i][j][K] + ss[j] - ss[i-1])\n",
    "        return dp[1][n][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "    \n",
    "        if (n - 1) % (k - 1) != 0:\n",
    "            return -1 \n",
    "    \n",
    "        prefix_sum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            prefix_sum[i + 1] = prefix_sum[i] + stones[i]\n",
    "        \n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        \n",
    "        for length in range(2, n + 1):\n",
    "            for i in range(n - length + 1):\n",
    "                j = i + length - 1\n",
    "                dp[i][j] = float('inf')\n",
    "                for mid in range(i, j, k - 1):\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid + 1][j])\n",
    "                if (length - 1) % (k - 1) == 0:\n",
    "                    dp[i][j] += prefix_sum[j + 1] - prefix_sum[i]\n",
    "\n",
    "        return dp[0][n - 1]\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "\n",
    "        # n = 1 + (k-1) * x 每次减少k-1堆\n",
    "        if (n-1) % (k-1) != 0:\n",
    "            return -1\n",
    "\n",
    "        prefixSum = [0] * (n+1)\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            prefixSum[i] = prefixSum[i-1] + stones[i-1]\n",
    "\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for step in range(k, n+1):\n",
    "            for i in range(n):\n",
    "                j = i + step - 1\n",
    "                if j >= n:\n",
    "                    break\n",
    "\n",
    "                dp[i][j] = float('inf')\n",
    "                #每次+ K-1 \n",
    "                for t in range(i, j, k-1):\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][t] + dp[t+1][j])\n",
    "                \n",
    "                # 如果能合成一堆 +上cost i到j的和\n",
    "                if (j -i) %(k-1) == 0:\n",
    "                    dp[i][j] += prefixSum[j+1] - prefixSum[i]\n",
    "\n",
    "        return dp[0][n-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n-1) % (k-1) :\n",
    "            return -1 \n",
    "        dp = [[inf]*n for _ in range(n)]\n",
    "        s = list(accumulate(stones, initial=0)) \n",
    "        for i in range(n):\n",
    "            dp[i][i] = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                for m in range(i, j, k-1):\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][m] + dp[m+1][j])\n",
    "                if (j - i) % (k - 1) == 0:\n",
    "                    dp[i][j] += s[j+1] - s[i]\n",
    "        # f = [[0] * n for _ in range(n)]\n",
    "        # for i in range(n - 1, -1, -1):\n",
    "        #     for j in range(i + 1, n):\n",
    "        #         f[i][j] = min(f[i][m] + f[m + 1][j] for m in range(i, j, k - 1))\n",
    "        #         if (j - i) % (k - 1) == 0:  # 可以合并成一堆\n",
    "        #             f[i][j] += s[j + 1] - s[i]\n",
    "\n",
    "        # print(dp)\n",
    "        # print(f)\n",
    "        return dp[0][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1):  # 无法合并成一堆\n",
    "            return -1\n",
    "        s = list(accumulate(stones, initial=0))  # 前缀和\n",
    "        # @cache  # 缓存装饰器，避免重复计算 dfs 的结果\n",
    "        # def dfs(i: int, j: int) -> int:\n",
    "        #     if i == j:  # 只有一堆石头，无需合并\n",
    "        #         return 0\n",
    "        #     res = min(dfs(i, m) + dfs(m + 1, j) for m in range(i, j, k - 1))\n",
    "        #     if (j - i) % (k - 1) == 0:  # 可以合并成一堆\n",
    "        #         res += s[j + 1] - s[i]\n",
    "        #     return res\n",
    "        # return dfs(0, n - 1)\n",
    "\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                f[i][j] = inf\n",
    "                for m in range(i, j, k - 1):\n",
    "                    f[i][j] = min(f[i][j], f[i][m] + f[m + 1][j])\n",
    "                if (j - i) % (k - 1) == 0:  # 可以合并成一堆\n",
    "                    f[i][j] += s[j + 1] - s[i]\n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "    \n",
    "        if (n - 1) % (k - 1) != 0:\n",
    "            return -1 \n",
    "    \n",
    "        prefix_sum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            prefix_sum[i + 1] = prefix_sum[i] + stones[i]\n",
    "        \n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        \n",
    "        for length in range(2, n + 1):\n",
    "            for i in range(n - length + 1):\n",
    "                j = i + length - 1\n",
    "                dp[i][j] = float('inf')\n",
    "                for mid in range(i, j, k - 1):\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid + 1][j])\n",
    "                if (length - 1) % (k - 1) == 0:\n",
    "                    dp[i][j] += prefix_sum[j + 1] - prefix_sum[i]\n",
    "\n",
    "        return dp[0][n - 1]\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1): return -1\n",
    "        s = list(accumulate(stones, initial=0))\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                f[i][j] = min(f[i][m] + f[m + 1][j] for m in range(i, j, k - 1))\n",
    "                if not (j - i) % (k - 1): f[i][j] += s[j + 1] - s[i]\n",
    "        return f[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        N = len(stones)\n",
    "        if (N - 1) % (k - 1):\n",
    "            return -1\n",
    "        s = list(accumulate(stones, initial=0))\n",
    "        dp = [[0]*N for _ in range(N)]\n",
    "        for i in range(N-1, -1, -1):\n",
    "            for j in range(i+1, N):\n",
    "                dp[i][j] = min(dp[i][m] + dp[m+1][j] for m in range(i, j, k-1))\n",
    "                if (j - i) % (k - 1) == 0:\n",
    "                    dp[i][j] += s[j+1] - s[i]\n",
    "        return dp[0][-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n - k) % (k - 1):\n",
    "            return -1\n",
    "        s = list(accumulate(stones, initial=0))\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in reversed(range(n)):\n",
    "            for j in range(i + 1, n):\n",
    "                f[i][j] = min(f[i][m] + f[m + 1][j] for m in range(i, j, k - 1))\n",
    "                if (j - i) % (k - 1) == 0:\n",
    "                    f[i][j] += s[j + 1] - s[i]\n",
    "        return f[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1):  # 无法合并成一堆\n",
    "            return -1\n",
    "        s = list(accumulate(stones, initial=0))  # 前缀和\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                f[i][j] = min(f[i][m] + f[m + 1][j] for m in range(i, j, k - 1))\n",
    "                if (j - i) % (k - 1) == 0:  # 可以合并成一堆\n",
    "                    f[i][j] += s[j + 1] - s[i]\n",
    "        return f[0][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1):  # 无法合并成一堆\n",
    "            return -1\n",
    "        s = list(accumulate(stones, initial=0))  # 前缀和\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                f[i][j] = min(f[i][m] + f[m + 1][j] for m in range(i, j, k - 1))\n",
    "                if (j - i) % (k - 1) == 0:  # 可以合并成一堆\n",
    "                    f[i][j] += s[j + 1] - s[i]\n",
    "        return f[0][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n-1) % (k-1) != 0:\n",
    "            return -1\n",
    "        presum = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            presum[i+1] = stones[i] + presum[i]\n",
    "\n",
    "        # dp[i][j]: min cost to combine stones into < k piles\n",
    "        dp = [[float('inf')] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i, n):\n",
    "                if i == j:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    for m in range(i, j, k-1):\n",
    "                        # print(i, j, m)\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][m]+dp[m+1][j])\n",
    "                    if (j-i) % (k-1) == 0:\n",
    "                        dp[i][j] += presum[j+1] - presum[i]\n",
    "        \n",
    "        # print(dp)\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1): return -1\n",
    "        s = list(accumulate(stones, initial=0))\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                f[i][j] = min(f[i][m] + f[m + 1][j] for m in range(i, j, k - 1))\n",
    "                if not (j - i) % (k - 1): f[i][j] += s[j + 1] - s[i]\n",
    "        return f[0][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones1(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        s = list(accumulate(stones, initial=0))  # 前缀和\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i,j):\n",
    "\n",
    "            if j-i+1 == k:\n",
    "                return s[j+1]-s[i]\n",
    "            if j-i+1 < k:\n",
    "                return inf\n",
    "            res = inf\n",
    "            for m in range(i,j,k-1):\n",
    "                res = min(res,dfs(i, m)+dfs(m+1,j))\n",
    "            return res\n",
    "        return dfs(0,n-1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # 合成一堆？，https://leetcode.cn/problems/minimum-cost-to-merge-stones/\n",
    "        n = len(stones)\n",
    "        #从 nnn 堆变成 1堆，需要减少 n−1堆。而每次合并都会减少 k−1 堆，所以 n−1必须是 k−1 的倍数。\n",
    "        if (n-1)%(k-1) != 0:\n",
    "            return -1\n",
    "\n",
    "        s = list(accumulate(stones, initial=0))  # 前缀和\n",
    "        # 最后一次合并的值肯定是sum(stones)\n",
    "        # print(s)\n",
    "       \n",
    "        @cache\n",
    "        def dfs(i,j): #去掉p参数\n",
    "            if i == j: #注意只有一堆，不需要合并，所以直接返回0\n",
    "                return 0\n",
    "            res = inf\n",
    "            for m in range(i,j,k-1):#计算所有方案，得到最小值\n",
    "                res = min(res,dfs(i,m)+dfs(m+1,j)) #枚举m时，保证m-i是k-1的倍数\n",
    "            if (j-i)%(k-1) == 0: \n",
    "                # == if (n-1)%(k-1) != 0,(j+1 -i -1),i从0 开始 ，表示能合成一堆\n",
    "                res += s[j+1]-s[i]\n",
    "            return res\n",
    "\n",
    "        return dfs(0,n-1)\n",
    "\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        # 合成一堆？，https://leetcode.cn/problems/minimum-cost-to-merge-stones/\n",
    "        n = len(stones)\n",
    "        #从 nnn 堆变成 1堆，需要减少 n−1堆。而每次合并都会减少 k−1 堆，所以 n−1必须是 k−1 的倍数。\n",
    "        if (n-1)%(k-1) != 0:\n",
    "            return -1\n",
    "\n",
    "        s = list(accumulate(stones, initial=0))  # 前缀和\n",
    "        # 最后一次合并的值肯定是sum(stones)\n",
    "        # print(s)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        # 区间dp,i<j\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                res = inf\n",
    "                for m in range(i,j,k-1):#枚举所有方案\n",
    "                    if (j-i)%(k-1) == 0:\n",
    "                        res = min(res,dp[i][m] + dp[m+1][j]+s[j+1]-s[i])\n",
    "                    else:\n",
    "                        res = min(res,dp[i][m] + dp[m+1][j])\n",
    "                dp[i][j] = res\n",
    "        return dp[0][n-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones1(self, stones: List[int], k: int) -> int:\n",
    "        # 合成一堆？，https://leetcode.cn/problems/minimum-cost-to-merge-stones/\n",
    "        n = len(stones)\n",
    "        #从 nnn 堆变成 1堆，需要减少 n−1堆。而每次合并都会减少 k−1 堆，所以 n−1必须是 k−1 的倍数。\n",
    "        if (n-1)%(k-1) != 0:\n",
    "            return -1\n",
    "\n",
    "        s = list(accumulate(stones, initial=0))  # 前缀和\n",
    "        # 最后一次合并的值肯定是sum(stones)\n",
    "        # print(s)\n",
    "       \n",
    "        @cache\n",
    "        def dfs(i,j): #去掉p参数\n",
    "            if i == j: #注意只有一堆，不需要合并，所以直接返回0\n",
    "                return 0\n",
    "            res = inf\n",
    "            for m in range(i,j,k-1):#计算所有方案，得到最小值\n",
    "                res = min(res,dfs(i,m)+dfs(m+1,j)) #枚举m时，保证m-i是k-1的倍数\n",
    "            if (j-i)%(k-1) == 0: \n",
    "                # == if (n-1)%(k-1) != 0,(j+1 -i -1),i从0 开始 ，表示能合成一堆\n",
    "                res += s[j+1]-s[i]\n",
    "            return res\n",
    "\n",
    "        return dfs(0,n-1)\n",
    "\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        # 合成一堆？，https://leetcode.cn/problems/minimum-cost-to-merge-stones/\n",
    "        n = len(stones)\n",
    "        #从 nnn 堆变成 1堆，需要减少 n−1堆。而每次合并都会减少 k−1 堆，所以 n−1必须是 k−1 的倍数。\n",
    "        if (n-1)%(k-1) != 0:\n",
    "            return -1\n",
    "\n",
    "        s = list(accumulate(stones, initial=0))  # 前缀和\n",
    "        # 最后一次合并的值肯定是sum(stones)\n",
    "        # print(s)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        # 区间dp,i<j\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                res = inf\n",
    "                for m in range(i,j,k-1):#枚举所有方案\n",
    "                    if (j-i)%(k-1) == 0:\n",
    "                        res = min(res,dp[i][m] + dp[m+1][j]+s[j+1]-s[i])\n",
    "                    else:\n",
    "                        res = min(res,dp[i][m] + dp[m+1][j])\n",
    "                dp[i][j] = res\n",
    "        return dp[0][n-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1) != 0:\n",
    "            return -1\n",
    "\n",
    "        d = [[[inf] * (k + 1) for _ in range(n)] for _ in range(n)]\n",
    "        sum = [0] * n\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            d[i][i][1] = 0\n",
    "            s += stones[i]\n",
    "            sum[i] = s\n",
    "\n",
    "        for L in range(2, n + 1):\n",
    "            for l in range(n - L + 1):\n",
    "                r = l + L - 1\n",
    "                for t in range(2, k + 1):\n",
    "                    for p in range(l, r, k - 1):\n",
    "                        d[l][r][t] = min(d[l][r][t], d[l][p][1] + d[p + 1][r][t - 1])\n",
    "                d[l][r][1] = min(d[l][r][1], d[l][r][k] + (sum[r] - (0 if l == 0 else sum[l - 1])))\n",
    "        return d[0][n - 1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], K: int) -> int:\n",
    "        n = len(stones)\n",
    "        # if n == 1: return 0\n",
    "        while n // K > 0:\n",
    "            n = n // K + n % K\n",
    "        if n != 1: return -1\n",
    "        \n",
    "        prefix = [0] + [*accumulate(stones)]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j):\n",
    "            if j - i + 1 < K: return 0\n",
    "            res = min(dp(i, mid) + dp(mid + 1, j) for mid in range(i, j, K - 1))\n",
    "            if (j - i) % (K - 1) == 0:\n",
    "                res += prefix[j + 1] - prefix[i]\n",
    "            return res\n",
    "        return dp(0, len(stones) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1) != 0:\n",
    "            return -1\n",
    "\n",
    "        d = [[[inf] * (k + 1) for _ in range(n)] for _ in range(n)]\n",
    "        sum = [0] * n\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            d[i][i][1] = 0\n",
    "            s += stones[i]\n",
    "            sum[i] = s\n",
    "\n",
    "        for L in range(2, n + 1):\n",
    "            for l in range(n - L + 1):\n",
    "                r = l + L - 1\n",
    "                for t in range(2, k + 1):\n",
    "                    for p in range(l, r, k - 1):\n",
    "                        d[l][r][t] = min(d[l][r][t], d[l][p][1] + d[p + 1][r][t - 1])\n",
    "                d[l][r][1] = d[l][r][k] + (sum[r] - (0 if l == 0 else sum[l - 1]))\n",
    "        return d[0][n - 1][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "\n",
    "        if (n - 1) % (k - 1) != 0:\n",
    "            return -1\n",
    "\n",
    "        # 计算前缀和\n",
    "        prefix_sum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            prefix_sum[i + 1] = prefix_sum[i] + stones[i]\n",
    "\n",
    "        # 记忆化搜索的辅助函数\n",
    "        @lru_cache(None)\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if j - i + 1 < k:\n",
    "                return 0\n",
    "            cost = 0\n",
    "            if (j - i) % (k - 1) == 0:\n",
    "                cost = prefix_sum[j + 1] - prefix_sum[i]\n",
    "\n",
    "            return cost + min(dfs(i, mid) + dfs(mid + 1, j) for mid in range(i, j, k - 1))\n",
    "\n",
    "        return dfs(0, n - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1):\n",
    "            return -1\n",
    "        # s = [0]\n",
    "        # for i in range(n):\n",
    "        #     s.append(s[-1] + stones[i])\n",
    "        s = list(accumulate(stones, initial=0))  # 前缀和\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j, p):\n",
    "        #     if p == 1:\n",
    "        #         return 0 if i == j else dfs(i, j, k) + s[j + 1] - s[i]\n",
    "        #     ans = inf\n",
    "        #     for m in range(i, j, k - 1):\n",
    "        #         ans = min(ans, dfs(i, m, 1) + dfs(m + 1, j, p - 1))\n",
    "        #     return ans\n",
    "        # return dfs(0, n - 1, 1)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == j:\n",
    "                return 0\n",
    "            ans = min(dfs(i, m) + dfs(m + 1, j) for m in range(i, j, k - 1) )\n",
    "            if (j - i) % (k - 1) == 0:\n",
    "                ans += s[j + 1] - s[i]\n",
    "            return ans\n",
    "        return dfs(0, n - 1)\n",
    "            \n",
    "            \n",
    "            \n",
    "\n",
    "            \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], K: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (K - 1):\n",
    "            return -1\n",
    "        s = list(accumulate(stones, initial=0))\n",
    "        f = [[[inf] * (K + 1) for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            f[i][i][1] = 0\n",
    "        for l in range(2, n + 1):\n",
    "            for i in range(1, n - l + 2):\n",
    "                j = i + l - 1\n",
    "                for k in range(1, K + 1):\n",
    "                    for h in range(i, j):\n",
    "                        f[i][j][k] = min(f[i][j][k], f[i][h][1] + f[h + 1][j][k - 1])\n",
    "                f[i][j][1] = f[i][j][K] + s[j] - s[i - 1]\n",
    "        return f[1][n][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1):  # 无法合并成一堆\n",
    "            return -1\n",
    "        s = list(accumulate(stones, initial=0))  # 前缀和\n",
    "        @cache  # 缓存装饰器，避免重复计算 dfs 的结果\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i == j:  # 只有一堆石头，无需合并\n",
    "                return 0\n",
    "            res = min(dfs(i, m) + dfs(m + 1, j) for m in range(i, j, k - 1))\n",
    "            if (j - i) % (k - 1) == 0:  # 可以合并成一堆\n",
    "                res += s[j + 1] - s[i]\n",
    "            return res\n",
    "        return dfs(0, n - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if k > 2 and n % (k-1) != 1:\n",
    "            return -1\n",
    "        \n",
    "        pre = list(itertools.accumulate(stones, initial=0))\n",
    "        @cache\n",
    "        def f(i,j,p):\n",
    "            if p > j-i+1 or p == 0:\n",
    "                return math.inf\n",
    "            if p == j-i+1:\n",
    "                return 0\n",
    "            if p == 1:\n",
    "                return f(i,j,k) + pre[j+1] - pre[i]\n",
    "            ans = math.inf\n",
    "            l = 1\n",
    "            while j - (i+l) + 1 >= p-1:\n",
    "                ans = min(ans, f(i, i+l-1, 1) + f(i+l, j, p-1))\n",
    "                l += k-1\n",
    "            return ans\n",
    "        \n",
    "        return f(0, n-1, 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1) != 0:\n",
    "            return -1\n",
    "        prefix = [0] * (n + 1)\n",
    "\n",
    "        for i, v in enumerate(stones):\n",
    "            prefix[i + 1] = prefix[i] + v\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j, p) -> int:\n",
    "            if p == 1:\n",
    "                if i == j:\n",
    "                    return 0\n",
    "                return dfs(i, j, k) + prefix[j + 1] - prefix[i]\n",
    "\n",
    "            res = inf\n",
    "            for m in range(i, j, k - 1):\n",
    "                res = min(res, dfs(i, m, 1) + dfs(m + 1, j, p - 1))\n",
    "            return res\n",
    "\n",
    "        return dfs(0, n - 1, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        inf = 10**9\n",
    "        if (n-1)% (k-1) != 0:\n",
    "            return -1\n",
    "        dp = [[[inf for _ in range(k+1)] for _ in range(n+1)] for _ in range(n+1)]\n",
    "        dp[0][0][0] = 0\n",
    "        for i in range(n):\n",
    "            dp[i][i][1] = 0\n",
    "        for lens in range(2, n+1):\n",
    "            for l in range(n):\n",
    "                if l + lens > n:\n",
    "                    break\n",
    "                if lens == k:\n",
    "                    dp[l][l+lens-1][k] = 0\n",
    "                    dp[l][l+lens-1][1] = sum(stones[i] for i in range(l, l+lens)) + dp[l][l+lens-1][k]\n",
    "                else:\n",
    "                    for p in range(2, k+1):\n",
    "                        for p2 in range(l, l+lens, k-1):\n",
    "                            dp[l][l+lens-1][p] = min(dp[l][l+lens-1][p], dp[l][p2][1] + dp[p2+1][l+lens-1][p-1])        \n",
    "                    dp[l][l+lens-1][1] = sum(stones[i] for i in range(l, l+lens)) + dp[l][l+lens-1][k]\n",
    "        # print(dp[0][2], dp[1][2], dp[1][3])\n",
    "        return dp[0][n-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1) != 0:\n",
    "            return -1\n",
    "        prefix = [0] * (n + 1)\n",
    "        for i, v in enumerate(stones):\n",
    "            prefix[i + 1] = prefix[i] + v\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i == j:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for m in range(i, j, k - 1):\n",
    "                res = min(res, dfs(i, m) + dfs(m + 1, j))\n",
    "\n",
    "            if (j - i) % (k - 1) == 0:\n",
    "                res += prefix[j + 1] - prefix[i]\n",
    "            return res\n",
    "\n",
    "        return dfs(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n=len(stones)\n",
    "        if (n-1)%(k-1)!=0:\n",
    "            return -1\n",
    "        sum =[0]*(n+1) #合并在一起的消耗\n",
    "        s=0\n",
    "        for i in range(n):\n",
    "            s=stones[i]+s\n",
    "            sum[i+1]=s  #前合并i+1堆需要的成本\n",
    "        @cache  # 缓存装饰器，避免重复计算 dp 的结果\n",
    "        #定义计算最小化成本的函数\n",
    "        def dp(i,j,t):#i到j是索引区间，t是指合成几堆\n",
    "            if t==1:\n",
    "                if i==j:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return dp(i,j,k)+sum[j+1]-sum[i+1-1]\n",
    "            else:\n",
    "                return min(dp(i,p,1)+dp(p+1,j,t-1) for p in range(i,j,k-1)) \n",
    "        return dp(0,n-1,1)\n",
    "        #时间复杂度：\n",
    "        #空间复杂度：\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        #这里使用了前缀和优化求解sum_i^j(ai)的过程，定义一个前缀和数组\n",
    "        #mysum[i]表示前i个的和那么s[i]=mysum[i+1]-mysum[i],mysum[0]=0,便于我们直接求前k项和\n",
    "        mysum=[0]\n",
    "        n=len(stones)\n",
    "        tempsum=0\n",
    "        #无法合并的一开始就要判断，否则会无法终止递推\n",
    "        if (n-1)%(k-1):\n",
    "            return -1\n",
    "        for num in stones:\n",
    "            tempsum+=num\n",
    "            mysum.append(tempsum)\n",
    "        #定义dfs(i,j,p)表示把i到j（闭区间）范围内的石头合并为p堆所需的最小开销\n",
    "        #那么我们要求dfs(0,n-1,1),可以由最后p堆合并过来（考虑最后一步）\n",
    "        #dfs(i,j,1)=dfs(i,j,k)+sum(i,j)\n",
    "        #非一堆的情况可以考虑拆为1+p-1堆，这样合起来就是p堆\n",
    "        #dfs(i,j,p)=min(dfs(i,m,1)+dfs(m,j,p-1)),这里的m从i开始每次加k-1,因为你要保证它能被分出来（0个、k个2k-1）\n",
    "        #那n堆变成一堆，你要减少n-1堆，每次只能减少k-1堆，因此n-1%k-1为0才行，因此\n",
    "        #更进一步的优化可以把p去掉，因为可以利用整除判断p是否是1\n",
    "        @cache\n",
    "        def dfs(i,j,p):\n",
    "            nonlocal k\n",
    "            if p==1:\n",
    "                return 0 if i==j else dfs(i,j,k)+mysum[j+1]-mysum[i]\n",
    "            else:\n",
    "                return min([dfs(i,m,1)+dfs(m+1,j,p-1) for m in range(i,j,k-1)])\n",
    "        return dfs(0,n-1,1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1) != 0:\n",
    "            return -1\n",
    "        s = list(accumulate(stones, initial = 0))\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == j:\n",
    "                return 0\n",
    "            res = min(dfs(i, m) + dfs(m + 1, j) for m in range(i, j, k - 1))\n",
    "            if (j - i) % ( k - 1) == 0:\n",
    "                res += s[j + 1] - s[i]\n",
    "            return res\n",
    "        return dfs(0, n - 1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1):\n",
    "            return -1\n",
    "        pre = list(accumulate(stones, initial=0))\n",
    "        @cache\n",
    "        def dfs(i, j, p): # [i,j]合并成p堆\n",
    "            if p == 1:\n",
    "                if i == j: return 0\n",
    "                else:\n",
    "                    return dfs(i, j, k) + pre[j+1] - pre[i]\n",
    "            res = inf\n",
    "            for m in range(i, j, k - 1):\n",
    "                res = min(res, dfs(i, m, 1) + dfs(m+1, j, p-1))\n",
    "            return res\n",
    "\n",
    "        return dfs(0, n - 1, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        inf = 10**9\n",
    "        if (n-1)% (k-1) != 0:\n",
    "            return -1\n",
    "        dp = [[[inf for _ in range(k+1)] for _ in range(n+1)] for _ in range(n+1)]\n",
    "        dp[0][0][0] = 0\n",
    "        for i in range(n+1):\n",
    "            dp[i][i][1] = 0\n",
    "        for lens in range(2, n+1):\n",
    "            for l in range(n):\n",
    "                if l + lens > n:\n",
    "                    break\n",
    "                for p in range(1, k+1):\n",
    "                    for h in range(l, l+lens):\n",
    "                        dp[l][l+lens-1][p] = min(dp[l][l+lens-1][p], dp[l][h][1] + dp[h+1][l+lens-1][p-1])        \n",
    "                    dp[l][l+lens-1][1] = sum(stones[i] for i in range(l, l+lens)) + dp[l][l+lens-1][k]\n",
    "        # print(dp[0][2], dp[1][2], dp[1][3])\n",
    "        return dp[0][n-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # @cache\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n-1)%(k-1):\n",
    "            return -1\n",
    "        s = list(accumulate(stones,initial = 0)) #求前缀和，并补零\n",
    "        @cache\n",
    "        def dfs(i,j,p) ->int:\n",
    "            if p == 1 :\n",
    "                return 0 if i==j else dfs(i,j,k)+s[j+1]-s[i]\n",
    "            return min(dfs(i,m,1)+dfs(m+1,j,p-1) for m in range(i,j,k-1)) # 脑袋瓜子回去想（i，j,k-1）中j需不需要+1\n",
    "        return dfs(0,n-1,1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        s = list(accumulate(stones, initial=0))  # 前缀和\n",
    "        if (n-1)%(k-1) != 0:\n",
    "            return -1\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i,j):\n",
    "            if i == j: #注意只有一堆，不需要合并，所以直接返回0\n",
    "                return 0\n",
    "            res = inf\n",
    "            for m in range(i,j,k-1):\n",
    "                res = min(res,dfs(i, m)+dfs(m+1,j))\n",
    "            if (j-i)%(k-1) == 0:#最后整个区间合并\n",
    "                res +=  s[j+1]-s[i]\n",
    "            return res\n",
    "        return dfs(0,n-1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    #     # 合成一堆？，https://leetcode.cn/problems/minimum-cost-to-merge-stones/\n",
    "    #     n = len(stones)\n",
    "    #     #从 nnn 堆变成 1堆，需要减少 n−1堆。而每次合并都会减少 k−1 堆，所以 n−1必须是 k−1 的倍数。\n",
    "    #     if (n-1)%(k-1) != 0:\n",
    "    #         return -1\n",
    "\n",
    "    #     s = list(accumulate(stones, initial=0))  # 前缀和\n",
    "    #     # 最后一次合并的值肯定是sum(stones)\n",
    "    #     # print(s)\n",
    "       \n",
    "    #     @cache\n",
    "    #     def dfs(i,j): #去掉p参数\n",
    "    #         if i == j: #注意只有一堆，不需要合并，所以直接返回0\n",
    "    #             return 0\n",
    "    #         res = inf\n",
    "    #         for m in range(i,j,k-1):#计算所有方案，得到最小值\n",
    "    #             res = min(res,dfs(i,m)+dfs(m+1,j)) #枚举m时，保证m-i是k-1的倍数\n",
    "    #         if (j-i)%(k-1) == 0: \n",
    "    #             # == if (n-1)%(k-1) != 0,(j+1 -i -1),i从0 开始 ，表示能合成一堆\n",
    "    #             res += s[j+1]-s[i]\n",
    "    #         return res\n",
    "\n",
    "    #     return dfs(0,n-1)\n",
    "\n",
    "    # def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "    #     # 合成一堆？，https://leetcode.cn/problems/minimum-cost-to-merge-stones/\n",
    "    #     n = len(stones)\n",
    "    #     #从 nnn 堆变成 1堆，需要减少 n−1堆。而每次合并都会减少 k−1 堆，所以 n−1必须是 k−1 的倍数。\n",
    "    #     if (n-1)%(k-1) != 0:\n",
    "    #         return -1\n",
    "\n",
    "    #     s = list(accumulate(stones, initial=0))  # 前缀和\n",
    "    #     # 最后一次合并的值肯定是sum(stones)\n",
    "    #     # print(s)\n",
    "    #     dp = [[0]*n for _ in range(n)]\n",
    "    #     # 区间dp,i<j\n",
    "    #     for i in range(n-1,-1,-1):\n",
    "    #         for j in range(i+1,n):\n",
    "    #             res = inf\n",
    "    #             for m in range(i,j,k-1):#枚举所有方案\n",
    "    #                 if (j-i)%(k-1) == 0:\n",
    "    #                     res = min(res,dp[i][m] + dp[m+1][j]+s[j+1]-s[i])\n",
    "    #                 else:\n",
    "    #                     res = min(res,dp[i][m] + dp[m+1][j])\n",
    "    #             dp[i][j] = res\n",
    "    #     return dp[0][n-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n=len(stones)\n",
    "        if (n-1)%(k-1)!=0:\n",
    "            return -1\n",
    "        sum =[0]*(n+1) #合并在一起的消耗\n",
    "        s=0\n",
    "        for i in range(n):\n",
    "            s=stones[i]+s\n",
    "            sum[i+1]=s  #前合并i+1堆需要的成本\n",
    "        @cache  # 缓存装饰器，避免重复计算 dp 的结果\n",
    "        #定义计算最小化成本的函数\n",
    "        def dp(i,j,t):#i到j是索引区间，t是指合成几堆\n",
    "            if t==1:\n",
    "                if i==j:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return dp(i,j,k)+sum[j+1]-sum[i+1-1]\n",
    "            else:\n",
    "                return min(dp(i,p,1)+dp(p+1,j,t-1) for p in range(i,j,k-1)) \n",
    "        return dp(0,n-1,1)\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "\n",
    "        if (n-1) % (k-1) != 0:\n",
    "            return -1\n",
    "\n",
    "        s = [0] + stones\n",
    "        # presum list\n",
    "        for i in range(1,len(stones)+1):\n",
    "            s[i] += s[i-1]\n",
    "        # print(s)\n",
    "\n",
    "        @cache \n",
    "        def dfs(i, j, p):\n",
    "            if p == 1:\n",
    "                if i == j:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return dfs(i, j, k) + s[j+1] - s[i]\n",
    "            res= inf\n",
    "            for m in range(i, j, k-1):\n",
    "                res = min(res, dfs(i, m, 1) + dfs(m+1, j, p-1))\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, n-1, 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1):\n",
    "            return -1\n",
    "        s = list(accumulate(stones, initial=0))\n",
    "        @cache\n",
    "        def dfs(i, j, p):\n",
    "            if p == 1:\n",
    "                return 0 if i == j else dfs(i, j, k) + s[j+1] - s[i]\n",
    "            return min(dfs(i, m, 1) + dfs(m+1, j, p-1) for m in range(i, j, k-1))\n",
    "        return dfs(0, n-1, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1):  # 无法合并成一堆\n",
    "            return -1\n",
    "        s = list(accumulate(stones, initial=0))  # 前缀和\n",
    "        @cache  # 缓存装饰器，避免重复计算 dfs 的结果\n",
    "        def dfs(i: int, j: int, p: int) -> int:\n",
    "            if p == 1:  # 合并成一堆\n",
    "                return 0 if i == j else dfs(i, j, k) + s[j + 1] - s[i]\n",
    "            return min(dfs(i, m, 1) + dfs(m + 1, j, p - 1) for m in range(i, j, k - 1))\n",
    "        return dfs(0, n - 1, 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n-1) % (k-1) != 0:\n",
    "            return -1\n",
    "        s = list(accumulate(stones,initial=0))\n",
    "        @cache\n",
    "        def dfs(i,j,p):\n",
    "            if p == 1:\n",
    "                return 0 if i==j else dfs(i,j,k) + s[j+1]-s[i]\n",
    "            res = inf\n",
    "            for m in range(i,j,k-1):\n",
    "                res = min(res, dfs(i,m,1) + dfs(m+1,j,p-1))\n",
    "            return res\n",
    "        return dfs(0,n-1,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # @cache\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n-1)%(k-1):\n",
    "            return -1\n",
    "        s = list(accumulate(stones,initial = 0))\n",
    "        @cache\n",
    "        def dfs(i,j,p)->int:\n",
    "            if p == 1:\n",
    "                return 0 if i==j else dfs(i,j,k)+s[j+1]-s[i] # 模拟最后一步\n",
    "            return min(dfs(i,m,1)+dfs(m+1,j,p-1) for m in range(i,j,k-1))\n",
    "        return dfs(0,n-1,1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1):  # 无法合并成一堆\n",
    "            return -1\n",
    "        s = list(accumulate(stones, initial=0))  # 前缀和\n",
    "        @cache  # 缓存装饰器，避免重复计算 dfs 的结果\n",
    "        def dfs(i: int, j: int, p: int) -> int:\n",
    "            if p == 1:  # 合并成一堆\n",
    "                return 0 if i == j else dfs(i, j, k) + s[j + 1] - s[i]\n",
    "            return min(dfs(i, m, 1) + dfs(m + 1, j, p - 1) for m in range(i, j, k - 1))\n",
    "        return dfs(0, n - 1, 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n=len(stones)\n",
    "        pre_sum=list(accumulate(stones,initial=0))\n",
    "        if (n - 1) % (k - 1):  # 无法合并成一堆\n",
    "            return -1\n",
    "        @cache\n",
    "        #省略不必要的状态\n",
    "        def dfs(i:int,j:int,p:int)->int:\n",
    "            if i==j:\n",
    "                # return 0\n",
    "                if p==1:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return -inf\n",
    "            if p==1:\n",
    "                return dfs(i,j,k)+pre_sum[j+1]-pre_sum[i]\n",
    "            return min(dfs(i,x,1)+dfs(x+1,j,p-1) for x in range(i,j,k-1))\n",
    "        return dfs(0,n-1,1)\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        # 无法合并成一堆的条件\n",
    "        if (n - 1) % (k - 1) != 0:\n",
    "            return -1\n",
    "\n",
    "        # 计算前缀和\n",
    "        prefix_sum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            prefix_sum[i + 1] = prefix_sum[i] + stones[i]\n",
    "\n",
    "        # 用于获取i到j的总和\n",
    "        def get_range_sum(i, j):\n",
    "            return prefix_sum[j + 1] - prefix_sum[i]\n",
    "\n",
    "        # 初始化记忆数组\n",
    "        memo = {}\n",
    "\n",
    "        # 定义dfs搜索\n",
    "        def dfs(i, j, m):\n",
    "            # 若当前[i, j]之间有m堆石子\n",
    "            if (j - i + 1 - m) % (k - 1):\n",
    "                return float('inf')\n",
    "            \n",
    "            if (i, j, m) in memo:\n",
    "                return memo[(i, j, m)]\n",
    "\n",
    "            # 如果只有一堆则无成本\n",
    "            if i == j:\n",
    "                return 0 if m == 1 else float('inf')\n",
    "\n",
    "            # 如果合并成一堆\n",
    "            if m == 1:\n",
    "                memo[(i, j, m)] = dfs(i, j, k) + get_range_sum(i, j)\n",
    "                return memo[(i, j, m)]\n",
    "\n",
    "            # 遍历所有可能的分割点\n",
    "            cost = float('inf')\n",
    "            for mid in range(i, j, k - 1):\n",
    "                cost = min(cost, dfs(i, mid, 1) + dfs(mid + 1, j, m - 1))\n",
    "            \n",
    "            memo[(i, j, m)] = cost\n",
    "            return cost\n",
    "        \n",
    "        return dfs(0, n - 1, 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j, x):\n",
    "            # 设dfs(i,j,x)表示将i到j分为x堆需要的代价\n",
    "            if j - i + 1 < x:\n",
    "                # 数量少于堆数\n",
    "                return float(\"inf\")\n",
    "            if j - i + 1 == x:\n",
    "                # 数量等于堆数\n",
    "                return 0\n",
    "            if x == 1:\n",
    "                # 变成1堆前先变成k堆\n",
    "                return dfs(i, j, k) + pre[j + 1] - pre[i]\n",
    "            else:\n",
    "                # 先将i所在的堆算成1堆\n",
    "                return min(dfs(i, m, 1) + dfs(m + 1, j, x - 1) for m in range(i, j))\n",
    "        \n",
    "        # 可行性\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1) != 0:\n",
    "            return -1\n",
    "        # 前缀和\n",
    "        pre = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            pre[i + 1] = pre[i] + stones[i]\n",
    "        \n",
    "        # 区间DP\n",
    "        ans = dfs(0, n - 1, 1)\n",
    "        return ans if ans < float(\"inf\") else -1\n",
    "        # def dfs(cur_stonesm,k):\n",
    "        #     if len(cur_stones)<k:\n",
    "        #         return 0\n",
    "        #     if len(cur_stones) == k:\n",
    "        #         return sum(cur_stones)\n",
    "        #     minValue = float('inf')\n",
    "        #     for i in range(len(cur_stones)-2):\n",
    "        #         costs = sum(cur_stones[i:i+2])\n",
    "        #         minValue = min(minValue, costs+ dfs(cur_stones[i+1:],k))\n",
    "        #     return minValue\n",
    "        \n",
    "        # return dfs(stones,k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j, x):\n",
    "            # 设dfs(i,j,x)表示将i到j分为x堆需要的代价\n",
    "            if j - i + 1 < x:\n",
    "                # 数量少于堆数\n",
    "                return float(\"inf\")\n",
    "            if j - i + 1 == x:\n",
    "                # 数量等于堆数\n",
    "                return 0\n",
    "            if x == 1:\n",
    "                # 变成1堆前先变成k堆\n",
    "                return dfs(i, j, k) + pre[j + 1] - pre[i]\n",
    "            else:\n",
    "                # 先将i所在的堆算成1堆\n",
    "                return min(dfs(i, m, 1) + dfs(m + 1, j, x - 1) for m in range(i, j))\n",
    "        \n",
    "        # 可行性\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1) != 0:\n",
    "            return -1\n",
    "        # 前缀和\n",
    "        pre = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            pre[i + 1] = pre[i] + stones[i]\n",
    "        \n",
    "        # 区间DP\n",
    "        ans = dfs(0, n - 1, 1)\n",
    "        return ans if ans < float(\"inf\") else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        # 直接贪心，每次找最小值不可行，例如[6,4,4,6]\n",
    "        # n = len(stones)\n",
    "        # if (n - 1) % (k - 1) != 0:\n",
    "        #     return -1\n",
    "        # if n < k:\n",
    "        #     return -1\n",
    "        \n",
    "        # res = 0\n",
    "        # sums = [sum(stones[i:i+k]) for i in range(n-k+1)]\n",
    "        # lens = len(sums)\n",
    "        # while lens > 1:\n",
    "        #     min_v, min_idx = sums[0], 0\n",
    "        #     for idx in range(1, lens):\n",
    "        #         if sums[idx] < min_v:\n",
    "        #             min_v = sums[idx]\n",
    "        #             min_idx = idx\n",
    "        #     res += min_v\n",
    "\n",
    "        #     stones = stones[:min_idx] + [min_v] + stones[(min_idx + k):]\n",
    "        #     n = len(stones)\n",
    "        #     sums = [sum(stones[i:i+k]) for i in range(n-k+1)]\n",
    "        #     # print(stones, n, k)\n",
    "\n",
    "        #     lens = n - k + 1\n",
    "        # res += sum(stones)\n",
    "        # return res\n",
    "\n",
    "        # 参考https://leetcode.cn/problems/minimum-cost-to-merge-stones/solution/he-bing-shi-tou-de-zui-di-cheng-ben-by-l-pnvh/\n",
    "        # 动态规划：dp[i][j][z]表示i->j合成z堆最小成本，最终合并到1堆时一定是之前k堆的各自成本加所有石子之和，用递归的思想更好理解一些\n",
    "        # dfs[0][n-1][1] = dfs[0][n-1][k] + SUM(stones)\n",
    "        # 递归的做法：https://leetcode.cn/problems/minimum-cost-to-merge-stones/solution/tu-jie-qu-jian-dpzhuang-tai-she-ji-yu-yo-ppv0/\n",
    "        \n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1):\n",
    "            return -1\n",
    "        dp = [[[-1 for _ in range(k + 1)] for _ in range(n)] for _ in range(n)]\n",
    "        s = [0] + list(accumulate(stones)) # 计算前缀和\n",
    "        def dfs(i, j, p):\n",
    "            # print(i, j, p)\n",
    "            if dp[i][j][p] != -1:\n",
    "                return dp[i][j][p]\n",
    "            if p == 1:\n",
    "                res = 0 if i == j else dfs(i, j, k) + s[j + 1] - s[i]\n",
    "                dp[i][j][p] = res\n",
    "                return res\n",
    "            res = min(dfs(i, m, 1) + dfs(m + 1, j, p - 1) for m in range(i, j, k - 1))\n",
    "            dp[i][j][p] = res\n",
    "            return res\n",
    "        return dfs(0, n - 1, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n - 1) % (k - 1):\n",
    "            return -1\n",
    "        s = list(accumulate(stones, initial=0))\n",
    "        @cache  \n",
    "        def dfs(i: int, j: int, p: int) -> int:\n",
    "            if p == 1:\n",
    "                print(i, j, k, s[j + 1] - s[i])\n",
    "                return 0 if i == j else dfs(i, j, k) + s[j + 1] - s[i]\n",
    "            return min(dfs(i, m, 1) + dfs(m + 1, j, p - 1) for m in range(i, j, k - 1))\n",
    "        return dfs(0, n - 1, 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        L=len(stones)\n",
    "        if L==1:\n",
    "            return 0\n",
    "        @cache\n",
    "        def dfs(i,j,t) -> int:\n",
    "            n=len(stones[i:j])\n",
    "            #print(stones,i,j,t)\n",
    "            if n==t:\n",
    "                #print(0)\n",
    "                return 0\n",
    "            if t==1:\n",
    "                #print(sum(stones[i:j]))\n",
    "                p1=dfs(i,j,k)\n",
    "                if p1!=-1:\n",
    "                    return p1+sum(stones[i:j])\n",
    "                else:\n",
    "                    return -1\n",
    "            if n<t and n>0 or t==0:\n",
    "                #print(-1)\n",
    "                return -1\n",
    "            res=[]\n",
    "            for s in range(i+1,j):\n",
    "                p1=dfs(i,s,1)\n",
    "                p2=dfs(s,j,t-1)\n",
    "                if p1!=-1 and p2!=-1:\n",
    "                    res.append(p1+p2)\n",
    "            #print(res)\n",
    "            if res:\n",
    "                return min(res)\n",
    "            else:\n",
    "                return -1      \n",
    "        ans = dfs(0,L,k)\n",
    "        if ans==-1:\n",
    "            return -1\n",
    "        return ans+sum(stones)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# from linecache import cache\n",
    "# from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        S = [0]*(n+1)\n",
    "        for i in range(len(stones)):\n",
    "            S[i + 1] = S[i] + stones[i]\n",
    "        @cache\n",
    "        def dfs(left,right,div):\n",
    "            if (right - left + 1) < div:\n",
    "                return 10**9\n",
    "            elif (right - left + 1) == div:\n",
    "                return S[right+1] - S[left]\n",
    "            # 还可以再细分\n",
    "            if div == 1:\n",
    "                return dfs(left,right,k) + S[right + 1] - S[left]\n",
    "            ans = 10**9\n",
    "            for i in range(left,right):\n",
    "                ans = min(ans,dfs(left,i,1) + dfs(i+1,right,div - 1))\n",
    "            return ans\n",
    "        ans = dfs(0,n - 1,k)\n",
    "        return ans if ans < 10**9 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 1000. 合并石头的最低成本\n",
    "from typing import List\n",
    "from functools import cache\n",
    "from itertools import accumulate\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        s = list(accumulate(stones, initial=0))\n",
    "\n",
    "        @cache\n",
    "        def dfs(l, r, t):\n",
    "            if l == r and t == 1:\n",
    "                return 0\n",
    "            ans = int(1e9)\n",
    "            if t > r - l + 1:\n",
    "                return ans\n",
    "            if t == 1:\n",
    "                return dfs(l, r, k) + s[r + 1] - s[l]\n",
    "            for p in range(l, r):\n",
    "                ans = min(ans, dfs(l, p, 1) + dfs(p + 1, r, t - 1))\n",
    "            return ans\n",
    "\n",
    "        if (len(stones) - 1) % (k - 1) != 0:\n",
    "            return -1\n",
    "        return dfs(0, len(stones) - 1, 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        # unable to handle 看题解了。。。\n",
    "        n = len(stones)\n",
    "        if (n-1) % (k-1) != 0:\n",
    "            return -1\n",
    "        \n",
    "        dp = [[[-1 for i in range(k+1)] for j in range(n)] for l in range(n)]\n",
    "        preSum = [0 for i in range(n+1)]\n",
    "        for i in range(n):\n",
    "            preSum[i+1] = preSum[i] + stones[i]\n",
    "        for i in range(n):\n",
    "            dp[i][i][1] = 0\n",
    "\n",
    "        @cache\n",
    "        def dfs(l, r, t):\n",
    "            nonlocal dp\n",
    "            nonlocal preSum\n",
    "            nonlocal k\n",
    "            if dp[l][r][t] != -1: # dfs过\n",
    "                return dp[l][r][t]\n",
    "\n",
    "            if r-l+1 < t: # 不成立\n",
    "                return -1\n",
    "            \n",
    "            if t == 1:\n",
    "                val = dfs(l, r, k)\n",
    "                if val == -1:\n",
    "                    return -1\n",
    "                dp[l][r][t] = val + (preSum[r+1]-preSum[l])\n",
    "                return dp[l][r][t]\n",
    "            \n",
    "            val = 1e9\n",
    "            for p in range(l, r, k-1):\n",
    "                val1 = dfs(l, p, 1)\n",
    "                val2 = dfs(p+1, r, t-1)\n",
    "                if val1 == -1 or val2 == -1:\n",
    "                    continue\n",
    "                else:\n",
    "                    val = min(val, dfs(l, p, 1) + dfs(p+1, r, t-1))\n",
    "            if val == 1e9:\n",
    "                val = -1\n",
    "            \n",
    "            dp[l][r][t] = val\n",
    "            return val\n",
    "\n",
    "        return dfs(0, n-1, 1)\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "                \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        # unable to handle 看题解了。。。\n",
    "        n = len(stones)\n",
    "        if (n-1) % (k-1) != 0:\n",
    "            return -1\n",
    "        \n",
    "        dp = [[[-1 for i in range(k+1)] for j in range(n)] for l in range(n)]\n",
    "        preSum = [0 for i in range(n+1)]\n",
    "        for i in range(n):\n",
    "            preSum[i+1] = preSum[i] + stones[i]\n",
    "        for i in range(n):\n",
    "            dp[i][i][1] = 0\n",
    "\n",
    "        @cache\n",
    "        def dfs(l, r, t):\n",
    "            nonlocal dp\n",
    "            nonlocal preSum\n",
    "            nonlocal k\n",
    "            if dp[l][r][t] != -1: # dfs过\n",
    "                return dp[l][r][t]\n",
    "\n",
    "            if r-l+1 < t: # 不成立\n",
    "                return -1\n",
    "            \n",
    "            if t == 1:\n",
    "                val = dfs(l, r, k)\n",
    "                if val == -1:\n",
    "                    return -1\n",
    "                dp[l][r][t] = val + (preSum[r+1]-preSum[l])\n",
    "                return dp[l][r][t]\n",
    "            \n",
    "            val = 1e9\n",
    "            for p in range(l, r, k-1):\n",
    "                val1 = dfs(l, p, 1)\n",
    "                val2 = dfs(p+1, r, t-1)\n",
    "                if val1 == -1 or val2 == -1:\n",
    "                    continue\n",
    "                else:\n",
    "                    val = min(val, dfs(l, p, 1) + dfs(p+1, r, t-1))\n",
    "            if val == 1e9:\n",
    "                val = -1\n",
    "            \n",
    "            dp[l][r][t] = val\n",
    "            return val\n",
    "\n",
    "        return dfs(0, n-1, 1)\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "                \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "from math import inf\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: list, k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n-1)%(k-1):\n",
    "            return -1\n",
    "        @cache\n",
    "        def f(i,j,t):\n",
    "            if i==j and t==1:\n",
    "                return 0 \n",
    "            # elif j-i+1<t:\n",
    "            #     return 0 \n",
    "            elif t==1:\n",
    "                return f(i,j,k)+sum(stones[i:(j+1)])\n",
    "            else:\n",
    "                ans = inf\n",
    "                for p in range(i, j):\n",
    "                    ans = min(ans, f(i,p,1)+f(p+1,j,t-1))\n",
    "            return ans \n",
    "        return f(0, n-1, 1)\n",
    "    \n",
    "def main():\n",
    "    stones = [3,2,4,1]\n",
    "    K = 2\n",
    "    stones = [3,2,4,1]\n",
    "    K = 3\n",
    "    stones = [3,5,1,2,6]\n",
    "    K = 3\n",
    "    stones = [36,2,61,30,74,35,65,31,43,92,15,11,22]\n",
    "    K = 5\n",
    "    a = Solution()\n",
    "    print(a.mergeStones(stones, K))\n",
    "\n",
    "main()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        # unable to handle 看题解了。。。\n",
    "        n = len(stones)\n",
    "        if (n-1) % (k-1) != 0:\n",
    "            return -1\n",
    "        \n",
    "        dp = [[[-1 for i in range(k+1)] for j in range(n)] for l in range(n)]\n",
    "        preSum = [0 for i in range(n+1)]\n",
    "        for i in range(n):\n",
    "            preSum[i+1] = preSum[i] + stones[i]\n",
    "        for i in range(n):\n",
    "            dp[i][i][1] = 0\n",
    "\n",
    "        @cache\n",
    "        def dfs(l, r, t):\n",
    "            nonlocal dp\n",
    "            nonlocal preSum\n",
    "            nonlocal k\n",
    "            if dp[l][r][t] != -1: # dfs过\n",
    "                return dp[l][r][t]\n",
    "\n",
    "            if r-l+1 < t: # 不成立\n",
    "                return -1\n",
    "            \n",
    "            if t == 1:\n",
    "                val = dfs(l, r, k)\n",
    "                if val == -1:\n",
    "                    return -1\n",
    "                dp[l][r][t] = val + (preSum[r+1]-preSum[l])\n",
    "                return dp[l][r][t]\n",
    "            \n",
    "            val = 1e9\n",
    "            for p in range(l, r, k-1):\n",
    "                val1 = dfs(l, p, 1)\n",
    "                val2 = dfs(p+1, r, t-1)\n",
    "                if val1 == -1 or val2 == -1:\n",
    "                    continue\n",
    "                else:\n",
    "                    val = min(val, dfs(l, p, 1) + dfs(p+1, r, t-1))\n",
    "            if val == 1e9:\n",
    "                val = -1\n",
    "            \n",
    "            dp[l][r][t] = val\n",
    "            return val\n",
    "\n",
    "        return dfs(0, n-1, 1)\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "                \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        pre_sum = list(accumulate(stones, initial=0))\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j, p):\n",
    "            # print('------', i, j, p)\n",
    "            if p <= 0 or p > j - i:\n",
    "                return -1\n",
    "            if p == 1:\n",
    "                if j - i == 1:\n",
    "                    # print('0', i, j, p, 0)\n",
    "                    return 0\n",
    "                elif j - i < k:\n",
    "                    # print('0.5-', i, j, p, 0)\n",
    "                    return -1\n",
    "                else:\n",
    "                    # print('1', i, j, p, '->', k, pre_sum[j] - pre_sum[i])\n",
    "                    next_result = dfs(i, j, k)\n",
    "                    # 注意，需要判定next_result 是不是-1\n",
    "                    return -1 if next_result < 0 else next_result + pre_sum[j] - pre_sum[i] #这里需要注意，j - i计算的是，i ~ j-1的和，不应该包含j；\n",
    "            else:\n",
    "                min_v = float('inf')\n",
    "                for h in range(i + 1, j):\n",
    "                    part1 = dfs(i, h, 1)\n",
    "                    part2 = dfs(h, j, p - 1)\n",
    "                    if part1 >= 0 and part2 >= 0:\n",
    "                        # print('check1', i, h, 1)\n",
    "                        # print('check2', h, j, p - 1)\n",
    "                        min_v = min(min_v, part1 + part2) #注意，这里不需要再加sum()\n",
    "                # print('2', i, j, p, min_v == float('inf'))\n",
    "                return -1 if min_v == float('inf') else min_v\n",
    "        \n",
    "        return 0 if(len(stones) == 1) else dfs(0, len(stones), 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        self.k = k\n",
    "        if (n - 1) % (k-1) != 0:\n",
    "            return -1\n",
    "        self.pre_sum = [0]\n",
    "        for num in stones:\n",
    "            self.pre_sum.append(self.pre_sum[-1] + num)\n",
    "        \n",
    "        return self.dfs(0, n-1, 1)\n",
    "\n",
    "    @cache\n",
    "    def dfs(self, i,j,p):\n",
    "        if p == 1:\n",
    "            return 0 if i ==j else self.dfs(i,j,self.k) + self.pre_sum[j+1] - self.pre_sum[i]\n",
    "        \n",
    "        return min(self.dfs(i, m, 1) + self.dfs(m+1,j, p-1) for m in range(i,j,self.k-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], K: int) -> int:\n",
    "        acc = [0] + list(accumulate(stones))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j, k):\n",
    "            if k == 1:\n",
    "                if i == j - 1:\n",
    "                    return stones[i], 0\n",
    "                elif j - i == k:\n",
    "                    aa = acc[j] - acc[i]\n",
    "                    return aa, aa\n",
    "                else:\n",
    "                    x, c = dp(i, j, K)\n",
    "                    return x, x + c\n",
    "            if i >= j or k <= 0:\n",
    "                return inf, inf\n",
    "\n",
    "            minn = inf\n",
    "            t = inf, inf\n",
    "            for a in range(i, j - k + 1):\n",
    "                x1, c1 = dp(i, a + 1, 1)\n",
    "                x2, c2 = dp(a + 1, j, k - 1)\n",
    "                d = c1 + c2 + x1 + x2\n",
    "                if d < minn:\n",
    "                    minn = d\n",
    "                    t = (x1 + x2, c1 + c2)\n",
    "\n",
    "            return t[0], t[1]\n",
    "\n",
    "        dpa = dp(0, len(stones), 1)[1]\n",
    "\n",
    "        if isinf(dpa):\n",
    "            return -1\n",
    "        else:\n",
    "            return dpa\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        self.k = k\n",
    "\n",
    "        if (n-1)%(k-1) != 0:\n",
    "            return -1\n",
    "        \n",
    "        self.prefix_sum = [0]\n",
    "        for stone in stones:\n",
    "            self.prefix_sum.append(self.prefix_sum[-1] + stone)\n",
    "        \n",
    "        return self.get_cost(0, n-1, 1)\n",
    "\n",
    "    \n",
    "    @cache\n",
    "    def get_cost(self, left, right, t):\n",
    "        if left == right and t == 1:\n",
    "            return 0\n",
    "        \n",
    "\n",
    "        if t > right - left + 1:\n",
    "            return inf\n",
    "        \n",
    "        if t == 1:\n",
    "            cost_k = self.get_cost(left, right, self.k)\n",
    "            if cost_k == inf:\n",
    "                return inf\n",
    "\n",
    "            res = cost_k + self.prefix_sum[right+1] - self.prefix_sum[left]\n",
    "            return res\n",
    "        \n",
    "        res = inf\n",
    "        for p in range(left, right, self.k-1):\n",
    "            res = min(res, self.get_cost(left, p, 1) + self.get_cost(p+1, right, t-1))\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        if not stones:\n",
    "            return -1\n",
    "        \n",
    "        n = len(stones)\n",
    "        \n",
    "        if n == 1:\n",
    "            return 0\n",
    "        \n",
    "        if (n - k) % (k - 1) != 0:\n",
    "            return -1\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i,j,piles):\n",
    "            # base case\n",
    "            if i == j:\n",
    "                if piles == 1:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return inf\n",
    "                \n",
    "            if piles == 1:\n",
    "                return dfs(i,j,k) + sum(stones[i:j+1])\n",
    "            \n",
    "            val = inf\n",
    "\n",
    "\n",
    "            for s in range(i,j):\n",
    "                val = min(val, dfs(i,s,1) + dfs(s + 1,j,piles-1))\n",
    "            \n",
    "            return val\n",
    "                    \n",
    "                \n",
    "        \n",
    "        \n",
    "        \n",
    "        return dfs(0, n - 1, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        if (len(stones) - 1) % (k - 1) != 0:\n",
    "            return -1\n",
    "\n",
    "        self.stones = stones\n",
    "        self.k = k\n",
    "        return self.func1(0, len(stones), 1)\n",
    "    # 边界left包含 ，right不包含\n",
    "    @cache\n",
    "    def func1(self, left, right, n0):\n",
    "        n = right - left\n",
    "        if n < self.k:\n",
    "            assert n == n0\n",
    "            return 0\n",
    "        \n",
    "        if n == self.k:\n",
    "            assert n0 == 1\n",
    "            return sum(self.stones[left:right])\n",
    "\n",
    "        num = (self.k - 1) if n0 == 1 else n0 - 1\n",
    "        res = 0\n",
    "        for i in range(n):  # 让他足够大，不关心要循环多少次\n",
    "            bound = left + 1 + (self.k - 1) * i\n",
    "            if right-bound < num:\n",
    "                break\n",
    "            res1 = self.func1(left, bound, 1)\n",
    "            res2 = self.func1(bound, right, num)\n",
    "            if res == 0:\n",
    "                res = res1 + res2\n",
    "            else:\n",
    "                res = min(res, res1 + res2)\n",
    "        if n0 == 1:\n",
    "            return res + sum(self.stones[left:right])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        self.k = k\n",
    "        self.stones = stones\n",
    "        n = len(stones)\n",
    "        if (n-1) % (k-1) != 0:  # 检查是否有剩余石头无法合并\n",
    "            return -1\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        return self.func1(0, len(stones), 1)\n",
    "\n",
    "    @cache\n",
    "    def func1(self, ifrom, ito, n0):\n",
    "        stones = self.stones[ifrom:ito]\n",
    "        k = self.k\n",
    "        n = len(stones)\n",
    "        if n == 1:  # 只剩下1堆石头，返回0\n",
    "            assert n0 == 1\n",
    "            return 0\n",
    "        if n == k:  # 剩下的石头刚好为k堆，将其合并为一堆并返回合并的成本\n",
    "            assert n0 == 1\n",
    "            return sum(stones)\n",
    "        if n < k:  # 剩下的石头不足k堆，返回0\n",
    "            assert n == n0\n",
    "            return 0\n",
    "        min1 = -1\n",
    "        for i in range(n):\n",
    "            n1 = 1+i*(k-1)\n",
    "            if n1 >= n:\n",
    "                break\n",
    "            if n-n1+1 < n0:  # 剩余的石头不足以形成新的堆数，退出循环\n",
    "                break\n",
    "            num1 = self.func1(ifrom, ifrom+n1, 1)  # 前半段石头的合并成本\n",
    "            num2 = self.func1(ifrom+n1, ito, k-1 if n0 == 1 else n0-1)  # 后半段石头的合并成本\n",
    "            num3 = num1 + num2  # 总的合并成本\n",
    "            # if n0 = 1, then k-1\n",
    "            # if n0 = 2, then n0-1\n",
    "            min1 = num3 if min1 == -1 else min(min1,num3)  # 更新最小合并成本\n",
    "            #print(stones[:n1],stones[n1:],n0, 'get', num3)\n",
    "        if n0 == 1:\n",
    "            return min1 + sum(stones)  # 返回最小合并成本加上当前石头的数量\n",
    "        return min1  # 返回最小合并成本"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def f(i, j, piles):\n",
    "            # if j-i+1 < piles or (j-i+1)%(k-1) != piles%(k-1):\n",
    "            if j-i+1 < piles:\n",
    "                return math.inf\n",
    "            if i == j or j-i+1 == piles:\n",
    "            # if i == j:\n",
    "                return 0\n",
    "            if piles == 1:\n",
    "                return f(i,j,k) + sum(stones[i:j+1])\n",
    "      \n",
    "            res = math.inf\n",
    "            for l in range(i,j):\n",
    "                res = min(res, f(i,l,1) + f(l+1,j,piles-1))\n",
    "            return res\n",
    "\n",
    "\n",
    "        ans = f(0, len(stones)-1, 1)\n",
    "        return ans if ans < math.inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        self.stones = stones\n",
    "        self.k = k\n",
    "        n = len(self.stones)\n",
    "        if (n-1) % (self.k-1) != 0:\n",
    "            return -1\n",
    "        return self.func1(0,n,1)\n",
    "\n",
    "    @cache\n",
    "    def func1(self,left,right,n0):\n",
    "        print(left,right)\n",
    "        n = right - left\n",
    "        if n < self.k:\n",
    "            assert n == n0\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            assert n0 == 1\n",
    "            return 0\n",
    "        if n == self.k:\n",
    "            assert n0 == 1\n",
    "            return sum(self.stones[left:right])\n",
    "\n",
    "        base = (self.k-1) if n0 == 1 else n0-1\n",
    "        res = 0\n",
    "        for i in range(n):  # 让他足够大，不关心要循环多少次\n",
    "            bound = 1+(self.k-1)*i\n",
    "            if n - bound < base:\n",
    "                break\n",
    "            res1 = self.func1(left,left+bound,1)\n",
    "            res2 = self.func1(left+bound,right,base)\n",
    "            if res == 0:\n",
    "                res = res1+res2\n",
    "            else:\n",
    "                res = min(res, res1+res2)\n",
    "        if n0 == 1:\n",
    "            return res + sum(self.stones[left:right])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from cmath import inf\n",
    "from functools import cache\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if((n - k) % (k - 1) != 0):\n",
    "            return -1\n",
    "\n",
    "        s = [0] * (n+1)\n",
    "        for i, x in enumerate(stones):\n",
    "            s[i+1] = s[i] + x\n",
    "\n",
    "        # 从[i,j]分成q份\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, q: int) -> int:\n",
    "            length = j - i + 1\n",
    "\n",
    "            if(q == 1):\n",
    "                return 0 if j == i else s[j+1] - s[i] + dfs(i,j,k)\n",
    "\n",
    "            ans = inf\n",
    "            for m in range(i,j):\n",
    "                #[i,m] - [m+1,j]\n",
    "                w1 = dfs(i,m,1) \n",
    "                w2 = dfs(m+1,j,q-1)\n",
    "                t = w1 + w2\n",
    "                if(t < ans):\n",
    "                    # print(i, m, j, \"-> (i,m) = \", p, \"(m+1,j) =\", q, \", score = \", dfs(i,m,p), dfs(m+1,j,q-p), t)\n",
    "                    ans = t\n",
    "\n",
    "            return ans\n",
    "\n",
    "\n",
    "        return dfs(0,n-1,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n=len(stones)\n",
    "        if (n-1)%(k-1)!=0:\n",
    "            return -1\n",
    "        d=[[[float(\"inf\") for _ in range(k+1)]for _ in range(n)]for _ in range(n)]\n",
    "        pre=[0]*n\n",
    "        tmp=0\n",
    "        for i in range(n):\n",
    "            d[i][i][1]=0\n",
    "            tmp+=stones[i]\n",
    "            pre[i]=tmp\n",
    "        for L in range(2, n + 1):\n",
    "            for l in range(n - L + 1):\n",
    "                r = l + L - 1\n",
    "                for t in range(2, k + 1):\n",
    "                    for p in range(l, r, k - 1):\n",
    "                        d[l][r][t] = min(d[l][r][t], d[l][p][1] + d[p + 1][r][t - 1])\n",
    "                d[l][r][1] = min(d[l][r][1], d[l][r][k] + (pre[r] - (0 if l == 0 else pre[l - 1])))\n",
    "        return d[0][n - 1][1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if (n-1) % (k-1) != 0:\n",
    "            return -1\n",
    "        @cache\n",
    "        def dp(i, j, t):\n",
    "            if t == 1:\n",
    "                return (sum(stones[i:j+1]) + dp(i, j, k)) if i != j else 0\n",
    "            res = inf\n",
    "            for p in range(i, j):\n",
    "                res = min(res, dp(i, p, 1) + dp(p+1, j, t-1))\n",
    "            return res\n",
    "                \n",
    "        res = dp(0, len(stones)-1, 1)\n",
    "        return -1 if res == inf else res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n=len(stones)\n",
    "        if (n-1)%(k-1)!=0:\n",
    "            return -1\n",
    "        dp=[[[float(\"inf\") for _ in range(k+1)]for _ in range(n)]for _ in range(n)]\n",
    "        pre=[0]*n\n",
    "        tmp=0\n",
    "        for i in range(n):\n",
    "            dp[i][i][1]=0\n",
    "            tmp+=stones[i]\n",
    "            pre[i]=tmp\n",
    "        for L in range(2,n+1):\n",
    "            for l in range(n-L+1):\n",
    "                r=l+L-1\n",
    "                for t in range(2,k+1):\n",
    "                    for p in range(l,r,k-1):\n",
    "                        dp[l][r][t]=min(dp[l][r][t],dp[l][p][1]+dp[p+1][r][t-1])\n",
    "                dp[l][r][1]=min(dp[l][r][1],dp[l][r][k]+(pre[r]-(0 if l==0 else pre[l-1])))\n",
    "        return dp[0][n-1][1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,j,m):\n",
    "            if m == j - i:return 0\n",
    "            if m == 1:\n",
    "                return dfs(i,j,k) + suf[j] - suf[i]\n",
    "            ans = inf\n",
    "            for l in range(i+1,j):\n",
    "                ans = min(ans,dfs(i,l,1) + dfs(l,j,m-1))\n",
    "            return ans\n",
    "        n = len(stones)\n",
    "        suf = list(accumulate(stones,initial=0))\n",
    "        ans = dfs(0,n,1)\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#1,k,2k-1,3k-2\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        self.k = k\n",
    "        self.stones = stones\n",
    "        n = len(stones)\n",
    "        if (n-1) % (k-1) != 0:\n",
    "            return -1\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        return self.func1(0,len(stones), 1)\n",
    "\n",
    "    @cache\n",
    "    def func1(self, ifrom, ito, n0):\n",
    "        stones = self.stones[ifrom:ito]\n",
    "        k = self.k\n",
    "        n = len(stones)\n",
    "        if n == 1:\n",
    "            assert n0 == 1\n",
    "            return 0\n",
    "        if n == k:\n",
    "            assert n0 == 1\n",
    "            return sum(stones)\n",
    "        if n < k:\n",
    "            assert n == n0\n",
    "            return 0\n",
    "        min1 = -1\n",
    "        for i in range(n):\n",
    "            n1 = 1+i*(k-1)\n",
    "            if n1 >= n:\n",
    "                break\n",
    "            if n-n1+1<n0:\n",
    "                break\n",
    "            num1 = self.func1(ifrom, ifrom+n1, 1)\n",
    "            num2 = self.func1(ifrom+n1, ito, k-1 if n0 == 1 else n0-1)\n",
    "            num3 = num1 + num2\n",
    "            # if n0 = 1, then k-1\n",
    "            # if n0 = 2, then n0-1\n",
    "            min1 = num3 if min1 == -1 else min(min1,num3)\n",
    "            #print(stones[:n1],stones[n1:],n0, 'get', num3)\n",
    "        if n0 == 1:\n",
    "            return min1 + sum(stones)\n",
    "        return min1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        # dfs(i,j,p)表示把数组[i,j]合并成p堆的最小代价\n",
    "        # 枚举第一堆是怎么合并而来，进行状态转移\n",
    "        # p = 1 时，如果i==j，表示只有一堆石子，代价为零，否则转变为dfs(i,j,k)，表示从k堆合并到堆\n",
    "        n = len(stones)\n",
    "        if (n-1)%(k-1)!=0:\n",
    "            return -1\n",
    "        pre = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            pre[i] = pre[i-1]+stones[i-1]\n",
    "        \n",
    "        rec = [[[-1]*(k+1) for _ in range(n)] for _ in range(n)]\n",
    "        def dfs(i,j,p):\n",
    "            if p==1:\n",
    "                return 0 if i==j else dfs(i,j,k)+pre[j+1]-pre[i]\n",
    "            if rec[i][j][p]!=-1:\n",
    "                return rec[i][j][p]\n",
    "            min_res = float('inf')\n",
    "            for m in range(i,j,k-1):\n",
    "                min_res = min(min_res, dfs(i,m,1)+dfs(m+1,j,p-1))\n",
    "            rec[i][j][p] = min_res\n",
    "            return min_res\n",
    "\n",
    "        return dfs(0, n-1, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if not (k == 2 or n % (k-1) == 1):\n",
    "            return -1\n",
    "        pre_sum = [stones[0]]\n",
    "        for i in range(n):\n",
    "            pre_sum.append(pre_sum[-1] + stones[i])\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j, t):\n",
    "            # print(i, j, t)\n",
    "            if j - i + 1 == t:\n",
    "                return 0\n",
    "            if i == j and t == 1:\n",
    "                return 0\n",
    "            if j - i + 1 < k:\n",
    "                return inf\n",
    "            if t == 1:\n",
    "                return dfs(i, j, k) + (pre_sum[j+1]-pre_sum[i])\n",
    "\n",
    "            res = inf\n",
    "            for idx in range(i, j):\n",
    "                res = min(dfs(i, idx, 1) + dfs(idx+1, j, t-1), res)\n",
    "            return res\n",
    "        return dfs(0, n-1, 1)\n",
    "        # return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeStones(self, stones: List[int], k: int) -> int:\n",
    "        n = len(stones)\n",
    "        if not (k == 2 or n % (k-1) == 1):\n",
    "            return -1\n",
    "        pre_sum = [stones[0]]\n",
    "        for i in range(n):\n",
    "            pre_sum.append(pre_sum[-1] + stones[i])\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j, t):\n",
    "            # print(i, j, t)\n",
    "            if j - i + 1 == t:\n",
    "                return 0\n",
    "            if i == j and t == 1:\n",
    "                return 0\n",
    "            if j - i + 1 < k:\n",
    "                return inf\n",
    "            if t == 1:\n",
    "                return dfs(i, j, k) + (pre_sum[j+1]-pre_sum[i])\n",
    "\n",
    "            res = inf\n",
    "            for idx in range(i, j):\n",
    "                res = min(dfs(i, idx, 1) + dfs(idx+1, j, t-1), res)\n",
    "            return res\n",
    "        return dfs(0, n-1, 1)\n",
    "        # return dp[0][n-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
